In prior art computer systems using branch history tables (BHTs), each BHT entry contains fields that predict the taken or not taken branch path for each branch Instruction in an associated line of instructions in an instruction cache (I-cache). Each line of instructions contains N number of instruction locations, and each of the N instruction locations may contain any type of instruction, e.g. a branch instruction or a non-branch instruction. There are N number of BHT fields in any BHT entry respectively associated with the N instruction locations in the associated I-cache line. Each BHT field may be comprised of one or more bits, and is sometimes referred to as a counter field. In the detailed example described herein, each BHT field comprises a single bit.
Any distribution of instruction types may exist in any I-cache line. Accordingly, a line of instructions within any I-cache entry may contain no branch instruction, or any combination of branch and non-branch instructions. For example, each I-cache entry may comprise an instruction line with 8 locations, and each of these eight instruction locations may contain an unconditional branch instruction, a conditional branch instruction, a non-branch instruction, or any other type of instruction. Thus, any distribution of instruction types may exist in any I-cache line. For example, the I-cache may have 32 K line entries. The I-cache index locates both an I-cache entry in the I-cache and an associated BHT entry in the BHT. Further, each BHT entry contains 8 BHT fields (e.g. bits) which are respectively associated with the 8 instruction locations in the associated I-cache entry. The only BHT bits in the BHT entry which are predictively effective are those associated with a branch Instruction location, and the BHT bits associated with instruction locations containing non-branch instructions are ignored. For example, a BHT entry having a BHT bit set to a “1” state is predicting that a branch instruction in its associated location will be “taken”, i.e. jump to a non-sequential instruction location on its next execution in the program. A “0” state for this BHT bit predicts its associated conditional branch instruction will be “not taken”, i.e. go to the next sequential instruction location in the program. A BHT bit associated with an unconditional branch instruction is always set to the “1” state to indicate it is always “taken”. The state of a BHT bit associated with a non-branch instruction is ignored, regardless of whether it has a “1” or “0” state.
In the prior art, a new line of instructions may be fetched from an L2 cache into an I-cache entry and replace a line of instructions previously stored in that I-cache entry. However, the BHT entry associated with that I-cache entry is not replaced in the BHT when the instruction line is replaced in the I-cache entry. Whatever BHT prediction states exist in the BHT entry are assumed to be the predictions for the branch-instruction(s) in the newly fetched line, even though the new line probably has branch instructions in different locations than the replaced I-cache line, and even though the existing BHT predictions may have been generated for other branch instructions in the program. Hence, the BHT predictions for a replaced line have a significant chance of providing wrong predictions for the branch instructions in the line.
When a BHT prediction selects the wrong branch path in the program, a sequence of incorrect instructions are selected and executed, because the selection of the wrong branch path is not immediately detected, but is detected many instruction execution cycles later. After detection, instruction results for these wrong instructions are destroyed, and the branch path is belatedly reset to the correct branch path from which the program execution continues, and the wrong BHT branch prediction is corrected in the BHT. Hence, wrong BHT predictions may cause significant time loss during program execution due to their selection of incorrect branch paths. This increase in the program execution time causes a corresponding reduction in the processing rate of executing programs. The resetting of wrong branch paths and the correction of BHT erroneous predictions is taught in the U.S. Pat. No. 6,598,152, granted Jul. 22, 2003.
The statistical probability of BHT predictions being incorrect for a replaced line is variable. For example, if a newly fetched instruction line replaces a branch instruction with an unrelated branch instruction in the same I-cache location, the existing setting of its location associated BHT prediction Is expected to have a 50 percent probability of being correct (and a 50 percent chance of being wrong). But if the new branch Instruction in the newly fetched line replaces a non-branch instruction, and if this newly fetched instruction was the last branch instruction previously in that instruction location, its location-associated BHT prediction has better than a 90 percent probability of being correct.
In the known prior art of BHT branch prediction techniques, the predictions in the branch history table were lost when associated branch instructions were replaced in the I-cache. The subject invention may be used with some of these prior BHT branch prediction systems to improve their BHT prediction rates.